package basic.courseLearn05.problem;

import basic.courseLearn05.TreeNode;
import basic.courseLearn05.Utils;
import org.junit.Test;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;

//输出二叉树的宽度
public class BinaryTreeWidth {

    @Test
    public void test(){
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
//        root.left.right = new TreeNode(5);
//        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(7);
        new Utils().treePrint(root);

        System.out.println(widthOfBinaryTree_solution2(root));
    }


    /**
     * 输出二叉树的宽度，方法1：利用map
     * @param root 根节点
     * @return  二叉树的宽度
     */
    public int widthOfBinaryTree_solution1(TreeNode root) {
        //1. 定义变量
        int maxWidth = -1,currentLevel = 1,currentWidth = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        HashMap<TreeNode, Integer> map = new HashMap<>();
        //2. 入队前的准备
        if (root==null){
            return 0;
        }else {
            queue.add(root);
            map.put(root, 1);
        }
        //3. 开始循环
        while(queue.size()>0){
            TreeNode currentNode = queue.poll();
            Integer level = map.get(currentNode);
            if (level == currentLevel){     //同一层
                currentWidth++;
            }else{      //下一层
                maxWidth = Math.max(maxWidth, currentWidth);
                currentLevel = level;
                currentWidth = 1;
            }
            if (currentNode.left!=null){
                queue.add(currentNode.left);
                map.put(currentNode.left, level+1);
            }
            if (currentNode.right!=null){
                queue.add(currentNode.right);
                map.put(currentNode.right, level+1);
            }
        }
        //4. 返回结果
        return Math.max(maxWidth, currentWidth);
    }

    /**
     * 输出二叉树的宽度，方法2：利用指针
     * @param root 根节点
     * @return  二叉树的宽度
     */
    public int widthOfBinaryTree_solution2(TreeNode root) {
        //1. 定义变量
        TreeNode lastNode = root,nextLastNode = null;
        int maxWidth = 1,currentWidth = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        //2. 准备
        if (root==null){
            return 0;
        }else{
            queue.add(root);
        }
        //3. 开始循环
        while(queue.size()>0){
            TreeNode currentNode = queue.poll();
            if (currentNode.left!=null){
                queue.add(currentNode.left);
                nextLastNode = currentNode.left;
            }
            if (currentNode.right!=null){
                queue.add(currentNode.right);
                nextLastNode = currentNode.right;
            }
            if (currentNode == lastNode){
                currentWidth++;
                maxWidth = Math.max(maxWidth, currentWidth);
                lastNode = nextLastNode;
                currentWidth = 0;
            }else{
                currentWidth++;
            }
        }
        //4. 返回结果
        return maxWidth;
    }


}
